#include <stdio.h>
#include <stdlib.h>

#define SUCCESS 1
#define FAILURE 0
#define OK 2
#define OUTOFINDEX 0
#define TRUE 3
#define FALSE -3
#define ERROR 0

typedef int Status;
typedef int ElemSet;
//*****************线性链表*******************
typedef struct LNode{
	ElemSet data;
	struct LNode *next;
}LNode,*LinkList;

Status InitL2(LinkList* L,int *s,int len){
	*L=(struct LNode*)malloc(sizeof(LNode));
	if (*L==NULL) return SUCCESS;
	(*L)->next=NULL;
	struct LNode *p,*q;
	p=*L;
    int i;
	for(i=0;i<len;i++){
		q=(struct LNode*)malloc(sizeof(LNode));
		q->data=s[i];
		q->next=NULL;

		p->next=q;
		p=q;
	}
	return SUCCESS;
}
Status InitList(LinkList* LN,int* str,int len){
	*LN=(LinkList)malloc(sizeof(LNode));
	if(*LN==NULL) return FAILURE;
	(*LN)->next=NULL;
	int i;
	LinkList p;
	for(i=len;i>0;i--){
		p=(LinkList)malloc(sizeof(LNode));
		if(p==NULL) return FAILURE;
		p->data=str[i-1];
		p->next=(*LN)->next,(*LN)->next=p;
	}
	return SUCCESS;
}


Status DestoryList(LinkList L){
	LinkList p=L->next;
	while(p!=NULL) {
		free(L);
		L=p;
		p=p->next;
	}
	free(L);
	return SUCCESS;
}

Status ClearList(LinkList L){
	LinkList p=L->next,r=p->next;
	while(r!=NULL){
		free(p);
		p=r;
		r=r->next;
	}
	free(p);
	L->next=NULL;
	return SUCCESS;
}

Status ListEmpty(LinkList L){
	if(L->next==NULL) return TRUE;
	return FALSE;
}

int ListLength(LinkList L){
	int len=0;
	LinkList p=L->next;
	while(p!=NULL){
		len++;
		p=p->next;
	}
	return len;
} 

Status GetElem(LinkList L,int i,ElemSet* e){
	LinkList p=L->next;
	int counter=1;
	while(p!=NULL && counter++<i){
		p=p->next;
	}
	if(p==NULL) return OUTOFINDEX;
	*e=p->data;
	return OK;
}

int LocatElem(LinkList L,ElemSet e,int (*FUNC)(LinkList L,ElemSet e)){
	int index=(*FUNC)(L,e);
	if(index) return index;
	return ERROR;
}

Status PriorElem(LinkList L,ElemSet cur_e,ElemSet* e){
	LinkList r,p=L->next;
	r=p->next;
	while(r!=NULL){
		if(r->data==cur_e) return p->data;
		p=r;
		r=r->next;
	}
	return ERROR;
}

Status NextElem(LinkList L,ElemSet cur_e,ElemSet* e){
	LinkList r,p=L->next;
	r=p->next;
	while(r!=NULL){
		if(p->data==cur_e) return r->data;
		p=r;
		r=r->next;
	}
	return ERROR;
}

Status ListInsert(LinkList L,int i,ElemSet e){
	LinkList r,p=L;
	int index=1;
	while(p!=NULL && ++index<i){
		p=p->next;
	}
	if(p==NULL || index>i && index==1) return FAILURE;
	r=(LinkList)malloc(sizeof(LNode));
	r->data=e;
	r->next=p->next;
	p->next=r;
	return SUCCESS;
}

Status ListDelete(LinkList L,int i,ElemSet* e){
	LinkList r,p=L->next;
	if(i==1) {
		L->next=p->next;
		free(p);
		return SUCCESS;
	}
	int j=1;
	while(p!=NULL && ++j<i){
		p=p->next;
	}
	if(p==NULL || j>i) return FAILURE;
	r=p->next;
	p->next=r->next;
	*e=r->data;
	free(r);
	return SUCCESS;
	
}

int ListTravese(LinkList L,int (*FUNC)(LinkList L,ElemSet e)){
	LinkList p=L->next;
	while(p!=NULL){
		if(!(*FUNC)(L,p->data)) return FAILURE;
		p=p->next;
	}
	return SUCCESS;

}

Status ToString(LinkList L,char* str){
	LinkList p=L->next;
	if(p==NULL) return FAILURE;
	sprintf(str,"%c ",'[');
	while(p!=NULL){
		sprintf(++(++str),"%c,",p->data);
		p=p->next;
	}
	sprintf(++str,"%c",']');
}

//对链表元素进行排序，L为头指针，ch为排序选择，非负为升序，负数为降序；
Status sort(LinkList L,int ch){
	LinkList r,p=L->next;
	ElemSet e;
	p=L->next,r=p->next;

	if(ch>=0){
		while(p->next!=NULL){
			while(r!=NULL){
				if(p->data > r->data) {
					e=p->data;
					p->data=r->data;
					r->data=e;
				}
				r=r->next;
			}
			p=p->next;
			r=p->next;
		}
		return SUCCESS;
	}
	else while(p->next!=NULL){
			while(r!=NULL){
				if(p->data < r->data) {
					e=p->data;
					p->data=r->data;
					r->data=e;
				}
				r=r->next;
			}
			p=p->next;
			r=p->next;
		}
		return SUCCESS;

}

//合并两个链表到第三个新的链表里
Status merger(LinkList la,LinkList lb,LinkList* lc){
	*lc=(LinkList)malloc(sizeof(LNode));
	(*lc)->next=NULL;
	LinkList pa=la->next;
	LinkList pb=lb->next;
	LinkList pc=*lc;

	while(pa!=NULL && pb!=NULL){
		if(pa->data < pb->data){
		 pc->next=pa;
		 pc=pa;
		 pa=pa->next;
		}
		else{
			pc->next=pb;
			pc=pb;
			pb=pb->next;
		}

	}
    if(pa==NULL) pc->next=pb;
    else pc->next=pa;
    la->next=NULL;
    lb->next=NULL;

	
	return SUCCESS;
}


